package com.itce.arco.test2;

import java.util.Arrays;
import java.util.HashMap;
import java.util.Map;

public class test3 {

    public static void main(String[] args) {

    }
//    题目一
/*给你两个整数数组 nums1 和 nums2 ，请你以数组形式返回两数组的交集。
    返回结果中每个元素出现的次数，应与元素在两个数组中都出现的次数一致
    （如果出现次数不一致，则考虑取较小值）。可以不考虑输出结果的顺序。
示例1
输入：nums1 = [1,2,2,1], nums2 = [2,2]
输出：[2,2]
示例2
输入：nums1 = [4,9,5], nums2 = [9,4,9,8,4]
输出：[4,9]
*/

public int[] intersect(int[] nums1,int[] nums2) {
    if (nums1.length<nums2.length) {
        intersect(nums2,nums1);
    }
    Map<Integer, Integer> hashMap = new HashMap<>();
    int count;
    for (int i = 0; i < nums1.length; i++) {
        count = hashMap.getOrDefault(nums1[i], 0);
        count++;
        hashMap.put(nums1[i],count);
    }
    int[] resule = new int[nums1.length];
    int index = 0;
    for (int i = 0; i < nums2.length; i++) {
        count = hashMap.getOrDefault(nums2[i],0);
        if (count>0) {
            resule[index] = nums2[i];
            index++;
            count--;
            hashMap.put(nums2[i],count);
        }
    }
    return Arrays.copyOfRange(resule,0,index);
}

//    题目二
/*给定一个数组 prices ，它的第 i 个元素 prices[i] 表示一支给定股票第 i 天的价格。

    你只能选择 某一天 买入这只股票，并选择在 未来的某一个不同的日子 卖出该股票。设计一个算法来计算你所能获取的最大利润。

    返回你可以从这笔交易中获取的最大利润。如果你不能获取任何利润，返回 0 。*/
/*    输入：[7,1,5,3,6,4]
    输出：5
    解释：在第 2 天（股票价格 = 1）的时候买入，在第 5 天（股票价格 = 6）的时候卖出，最大利润 = 6-1 = 5 。
    注意利润不能是 7-1 = 6, 因为卖出价格需要大于买入价格；同时，你不能在买入前卖出股票。*/
//    示例二
/*    输入：prices = [7,6,4,3,1]
    输出：0
    解释：在这种情况下, 没有交易完成, 所以最大利润为 0。*/
    public int maxProfit(int[] nums) {
        int min = nums[0];
        int maxProfit = 0;
        for (int i = 0; i < nums.length; i++) {
            if (nums[i]<min){
                min = nums[i];
            }
            if (nums[i]-min>maxProfit) {
                maxProfit = nums[i]-min;
            }
        }
        return maxProfit;
    }

























//    题目一：方法一：哈希表
/*  由于同一个数字在两个数组中都可能出现多次，因此需要用哈希表存储每个数字出现的次数。
    对于一个数字，其在交集中出现的次数等于该数字在两个数组中出现次数的最小值。
    首先遍历第一个数组，并在哈希表中记录第一个数组中的每个数字以及对应出现的次数，然后遍历第二个数组，
    对于第二个数组中的每个数字，如果在哈希表中存在这个数字，
    则将该数字添加到答案，并减少哈希表中该数字出现的次数。
    为了降低空间复杂度，首先遍历较短的数组并在哈希表中记录每个数字以及对应出现的次数，然后遍历较长的数组得到交集。*/
/*class Solution {
    public int[] intersect(int[] nums1, int[] nums2) {
        if (nums1.length > nums2.length) {
            return intersect(nums2, nums1);
        }
        Map<Integer, Integer> map = new HashMap<Integer, Integer>();
        for (int num : nums1) {
            int count = map.getOrDefault(num, 0) + 1;
            map.put(num, count);
        }
        int[] intersection = new int[nums1.length];
        int index = 0;
        for (int num : nums2) {
            int count = map.getOrDefault(num, 0);
            if (count > 0) {
                intersection[index++] = num;
                count--;
                if (count > 0) {
                    map.put(num, count);
                } else {
                    map.remove(num);
                }
            }
        }
        return Arrays.copyOfRange(intersection, 0, index);
    }
}*/
// 方法二：
/*  如果两个数组是有序的，则可以使用双指针的方法得到两个数组的交集。
    首先对两个数组进行排序，然后使用两个指针遍历两个数组。
    初始时，两个指针分别指向两个数组的头部。每次比较两个指针指向的两个数组中的数字，
    如果两个数字不相等，则将指向较小数字的指针右移一位，如果两个数字相等，将该数字添加到答案，
    并将两个指针都右移一位。当至少有一个指针超出数组范围时，遍历结束。*/
/*class Solution {
    public int[] intersect(int[] nums1, int[] nums2) {
        Arrays.sort(nums1);
        Arrays.sort(nums2);
        int length1 = nums1.length, length2 = nums2.length;
        int[] intersection = new int[Math.min(length1, length2)];
        int index1 = 0, index2 = 0, index = 0;
        while (index1 < length1 && index2 < length2) {
            if (nums1[index1] < nums2[index2]) {
                index1++;
            } else if (nums1[index1] > nums2[index2]) {
                index2++;
            } else {
                intersection[index] = nums1[index1];
                index1++;
                index2++;
                index++;
            }
        }
        return Arrays.copyOfRange(intersection, 0, index);
    }
}*/


//    题目二
//    方法一
/*    假设给定的数组为：[7, 1, 5, 3, 6, 4]
    我们来假设自己来购买股票。随着时间的推移，每天我们都可以选择出售股票与否。那么，假设在第 i 天，如果我们要在今天卖股票，那么我们能赚多少钱呢？

    显然，如果我们真的在买卖股票，我们肯定会想：如果我是在历史最低点买的股票就好了！太好了，在题目中，我们只要用一个变量记录一个历史最低价格 minprice，
    我们就可以假设自己的股票是在那天买的。那么我们在第 i 天卖出股票能得到的利润就是 prices[i] - minprice。

    因此，我们只需要遍历价格数组一遍，记录历史最低点，然后在每一天考虑这么一个问题：如果我是在历史最低点买进的，那么我今天卖出能赚多少钱？当考虑完所有天数之时，
    我们就得到了最好的答案。*/

/*public class Solution {
    public int maxProfit(int prices[]) {
        int minprice = Integer.MAX_VALUE;
        int maxprofit = 0;
        for (int i = 0; i < prices.length; i++) {
            if (prices[i] < minprice) {
                minprice = prices[i];
            } else if (prices[i] - minprice > maxprofit) {
                maxprofit = prices[i] - minprice;
            }
        }
        return maxprofit;
    }
}*/

    //  方法二
    /*    我们需要找出给定数组中两个数字之间的最大差值（即，最大利润）。此外，第二个数字（卖出价格）必须大于第一个数字（买入价格）。*/
/*public class Solution {
    public int maxProfit(int[] prices) {
        int maxprofit = 0;
        for (int i = 0; i < prices.length - 1; i++) {
            for (int j = i + 1; j < prices.length; j++) {
                int profit = prices[j] - prices[i];
                if (profit > maxprofit) {
                    maxprofit = profit;
                }
            }
        }
        return maxprofit;
    }
}*/
}
